#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <stddef.h>  // 用于 size_t

// 置换类型枚举
typedef enum {
    EMPTY_DISPLACE,   // 恒等置换
    CYCLIC_DISPLACE,  // 轮换置换
    COMPOSITE_DISPLACE // 组合置换
} DisplaceType;

// 置换结构体（组合模式）
typedef struct DisplaceExpression {
    DisplaceType type;
    union {
        // 轮换置换：存储轮换位置（如 [1,2] 表示 1→2→1）
        struct {
            int *cyclic;
            int cyclic_len;
        };
        // 组合置换：存储子置换列表
        struct {
            struct DisplaceExpression **expressions;
            int expr_len;
        };
    };
} DisplaceExpression;

// -------------------------- 工具函数 --------------------------
// 检查值是否在数组中
static bool int_in_array(int val, const int *arr, int len) {
    for (int i = 0; i < len; i++) {
        if (arr[i] == val) return true;
    }
    return false;
}

// 查找数组中值的索引
static int find_int_index(int val, const int *arr, int len) {
    for (int i = 0; i < len; i++) {
        if (arr[i] == val) return i;
    }
    return -1; // 未找到
}

// 动态数组扩容（int类型）
static int *array_resize(int *arr, int old_len, int new_len) {
    int *new_arr = (int *)realloc(arr, new_len * sizeof(int));
    if (!new_arr) {
        fprintf(stderr, "内存分配失败！\n");
        exit(EXIT_FAILURE);
    }
    return new_arr;
}

// 复制单个元素（通用类型，按大小复制）
static void copy_element(void *dest, const void *src, size_t elem_size) {
    memcpy(dest, src, elem_size);
}

// -------------------------- 置换创建与销毁 --------------------------
// 创建恒等置换（单例模式，用静态变量实现）
DisplaceExpression *empty_displace_create(void) {
    static DisplaceExpression instance;
    static bool initialized = false;
    if (!initialized) {
        instance.type = EMPTY_DISPLACE;
        initialized = true;
    }
    return &instance;
}

// 创建轮换置换（输入轮换位置数组，如 [1,2]）
DisplaceExpression *cyclic_displace_create(const int *cyclic, int cyclic_len) {
    if (cyclic_len < 2) {
        fprintf(stderr, "轮换长度至少为2！\n");
        return empty_displace_create();
    }
    DisplaceExpression *expr = (DisplaceExpression *)malloc(sizeof(DisplaceExpression));
    if (!expr) return NULL;
    expr->type = CYCLIC_DISPLACE;
    expr->cyclic_len = cyclic_len;
    expr->cyclic = (int *)malloc(cyclic_len * sizeof(int));
    memcpy(expr->cyclic, cyclic, cyclic_len * sizeof(int));
    return expr;
}

// 创建组合置换（输入子置换列表）
DisplaceExpression *composite_displace_create(DisplaceExpression **exprs, int expr_len) {
    if (expr_len == 0) {
        return empty_displace_create();
    }
    if (expr_len == 1) {
        return exprs[0]; // 单个置换直接返回，无需组合
    }
    DisplaceExpression *expr = (DisplaceExpression *)malloc(sizeof(DisplaceExpression));
    if (!expr) return NULL;
    expr->type = COMPOSITE_DISPLACE;
    expr->expr_len = expr_len;
    expr->expressions = (DisplaceExpression **)malloc(expr_len * sizeof(DisplaceExpression *));
    memcpy(expr->expressions, exprs, expr_len * sizeof(DisplaceExpression *));
    return expr;
}

// 销毁置换（递归销毁子置换）
void displace_destroy(DisplaceExpression *expr) {
    if (!expr || expr->type == EMPTY_DISPLACE) return; // 恒等置换无需销毁

    if (expr->type == CYCLIC_DISPLACE) {
        free(expr->cyclic);
    } else if (expr->type == COMPOSITE_DISPLACE) {
        for (int i = 0; i < expr->expr_len; i++) {
            displace_destroy(expr->expressions[i]);
        }
        free(expr->expressions);
    }
    free(expr);
}

// -------------------------- 核心方法：apply 置换 --------------------------
// 轮换置换的apply实现（从后往前遍历，处理首尾）
// 入参：src - 原数组，dest - 输出数组（需提前分配内存），elem_size - 元素大小
static void cyclic_apply(const DisplaceExpression *expr, const void *src, void *dest,
                         int array_len, size_t elem_size) {
    // 先复制原数组到目标数组
    memcpy(dest, src, array_len * elem_size);

    int *cyclic = expr->cyclic;
    int len = expr->cyclic_len;
    if (len == 0) return;

    // 计算最后一个位置的元素地址（src[cyclic[len-1]]）
    const void *last_elem = (const char *)src + cyclic[len - 1] * elem_size;
    void *temp = malloc(elem_size);
    copy_element(temp, last_elem, elem_size); // 保存最后一个元素

    // 从后往前赋值：dest[cyclic[i]] = src[cyclic[i-1]]
    for (int i = len - 1; i > 0; i--) {
        int dest_pos = cyclic[i];
        int src_pos = cyclic[i - 1];
        if (dest_pos < 0 || dest_pos >= array_len || src_pos < 0 || src_pos >= array_len) {
            fprintf(stderr, "轮换位置超出数组范围！\n");
            free(temp);
            return;
        }
        const void *src_elem = (const char *)src + src_pos * elem_size;
        void *dest_elem = (char *)dest + dest_pos * elem_size;
        copy_element(dest_elem, src_elem, elem_size);
    }

    // 处理首尾：dest[cyclic[0]] = temp
    void *first_dest = (char *)dest + cyclic[0] * elem_size;
    copy_element(first_dest, temp, elem_size);
    free(temp);
}

// 组合置换的apply实现（按顺序执行子置换）
static void composite_apply(const DisplaceExpression *expr, const void *src, void *dest,
                           int array_len, size_t elem_size) {
    // 临时数组，用于存储中间结果
    void *temp = malloc(array_len * elem_size);
    copy_element(temp, src, array_len * elem_size); // 初始复制原数组

    // 依次应用每个子置换
    for (int i = 0; i < expr->expr_len; i++) {
        void *next_temp = malloc(array_len * elem_size);
        displace_apply(expr->expressions[i], temp, next_temp, array_len, elem_size);
        free(temp);
        temp = next_temp;
    }

    // 最终结果复制到dest
    copy_element(dest, temp, array_len * elem_size);
    free(temp);
}

// 公共apply接口：应用置换到数组
// 注意：dest需提前分配足够内存（array_len * elem_size 字节）
void displace_apply(const DisplaceExpression *expr, const void *src, void *dest,
                   int array_len, size_t elem_size) {
    if (!expr || !src || !dest || array_len <= 0 || elem_size <= 0) {
        fprintf(stderr, "无效参数！\n");
        return;
    }

    switch (expr->type) {
        case EMPTY_DISPLACE:
            // 恒等置换：直接复制原数组
            memcpy(dest, src, array_len * elem_size);
            break;
        case CYCLIC_DISPLACE:
            cyclic_apply(expr, src, dest, array_len, elem_size);
            break;
        case COMPOSITE_DISPLACE:
            composite_apply(expr, src, dest, array_len, elem_size);
            break;
        default:
            fprintf(stderr, "未知置换类型！\n");
            memcpy(dest, src, array_len * elem_size); // 默认返回原数组
            break;
    }
}

// -------------------------- 辅助方法：获取位置映射 --------------------------
// 获取单个位置经过置换后的下一个位置
static int displace_next(const DisplaceExpression *expr, int pos, int array_len) {
    if (expr->type == EMPTY_DISPLACE) return pos; // 恒等置换：映射到自身

    if (expr->type == CYCLIC_DISPLACE) {
        int idx = find_int_index(pos, expr->cyclic, expr->cyclic_len);
        if (idx == -1) return pos; // 不在轮换中，映射到自身
        // 轮换映射：cyclic[idx] → cyclic[(idx+1)%len]
        return expr->cyclic[(idx + 1) % expr->cyclic_len];
    }

    if (expr->type == COMPOSITE_DISPLACE) {
        // 组合置换：按顺序应用每个子置换，得到最终位置
        int current = pos;
        for (int i = 0; i < expr->expr_len; i++) {
            current = displace_next(expr->expressions[i], current, array_len);
        }
        return current;
    }

    return pos;
}

// 获取置换涉及的所有位置
static int *displace_get_positions(const DisplaceExpression *expr, int array_len, int *pos_len) {
    int *positions = NULL;
    *pos_len = 0;

    for (int i = 0; i < array_len; i++) {
        int next = displace_next(expr, i, array_len);
        if (next != i) { // 只保留非恒等映射的位置
            positions = array_resize(positions, *pos_len, *pos_len + 1);
            positions[*pos_len] = i;
            (*pos_len)++;
        }
    }

    return positions;
}

// -------------------------- 核心方法：化简置换 --------------------------
DisplaceExpression *displace_simplify(const DisplaceExpression *expr, int array_len) {
    if (expr->type == EMPTY_DISPLACE) return empty_displace_create();

    // 第一步：构建位置映射表（pos → next_pos）
    int pos_len = 0;
    int *positions = displace_get_positions(expr, array_len, &pos_len);
    if (pos_len == 0) {
        free(positions);
        return empty_displace_create(); // 无有效映射，返回恒等置换
    }

    // 构建映射表（用数组模拟map，索引为位置，值为下一个位置）
    int *pos_map = (int *)malloc(array_len * sizeof(int));
    for (int i = 0; i < array_len; i++) {
        pos_map[i] = displace_next(expr, i, array_len);
    }

    // 第二步：遍历映射表，生成不相交的轮换
    bool *visited = (bool *)calloc(array_len, sizeof(bool)); // 标记是否已处理
    int cyclic_count = 0;
    DisplaceExpression **cyclic_exprs = NULL;

    for (int i = 0; i < pos_len; i++) {
        int start = positions[i];
        if (visited[start] || pos_map[start] == start) continue;

        // 生成一个轮换
        int cyclic_len = 0;
        int *cyclic = NULL;
        int current = start;

        while (!visited[current] && pos_map[current] != current) {
            visited[current] = true;
            cyclic = array_resize(cyclic, cyclic_len, cyclic_len + 1);
            cyclic[cyclic_len] = current;
            cyclic_len++;
            current = pos_map[current];
        }

        // 创建轮换置换并添加到列表
        if (cyclic_len >= 2) { // 长度≥2才是有效轮换
            cyclic_exprs = (DisplaceExpression **)realloc(
                cyclic_exprs, (cyclic_count + 1) * sizeof(DisplaceExpression *)
            );
            cyclic_exprs[cyclic_count] = cyclic_displace_create(cyclic, cyclic_len);
            cyclic_count++;
        }
        free(cyclic);
    }

    // 第三步：根据轮换数量生成结果
    DisplaceExpression *result;
    if (cyclic_count == 0) {
        result = empty_displace_create();
    } else if (cyclic_count == 1) {
        result = cyclic_exprs[0]; // 单个轮换直接返回
    } else {
        result = composite_displace_create(cyclic_exprs, cyclic_count);
    }

    // 释放临时内存
    free(positions);
    free(pos_map);
    free(visited);
    if (cyclic_count > 1) free(cyclic_exprs); // 组合置换已持有子置换指针，仅释放列表

    return result;
}

// -------------------------- 测试工具：打印置换和数组 --------------------------
// 打印置换
void displace_print(const DisplaceExpression *expr) {
    if (!expr) return;
    switch (expr->type) {
        case EMPTY_DISPLACE:
            printf("恒等置换()");
            break;
        case CYCLIC_DISPLACE:
            printf("轮换(");
            for (int i = 0; i < expr->cyclic_len; i++) {
                printf("%d", expr->cyclic[i]);
                if (i != expr->cyclic_len - 1) printf(" ");
            }
            printf(")");
            break;
        case COMPOSITE_DISPLACE:
            printf("组合(");
            for (int i = 0; i < expr->expr_len; i++) {
                displace_print(expr->expressions[i]);
                if (i != expr->expr_len - 1) printf(" · ");
            }
            printf(")");
            break;
    }
}

// 打印字符数组（示例：可根据实际类型编写对应打印函数）
void print_char_array(const void *array, int len) {
    const char *arr = (const char *)array;
    printf("{");
    for (int i = 0; i < len; i++) {
        printf("'%c'", arr[i]);
        if (i != len - 1) printf(", ");
    }
    printf("}");
}

// 打印整数数组（示例：支持多类型）
void print_int_array(const void *array, int len) {
    const int *arr = (const int *)array;
    printf("{");
    for (int i = 0; i < len; i++) {
        printf("%d", arr[i]);
        if (i != len - 1) printf(", ");
    }
    printf("}");
}

// -------------------------- 测试主函数 --------------------------
int main() {
    // 测试1：单个轮换置换 (1 2) 作用于字符数组 {'A','B','C'}
    printf("=== 测试1：单个轮换置换 (1 2) 作用于字符数组 ===\n");
    int cyclic1[] = {1, 2}; // 轮换 (1→2→1)
    DisplaceExpression *cyclic_expr = cyclic_displace_create(cyclic1, sizeof(cyclic1)/sizeof(int));
    char array1[] = {'A', 'B', 'C'};
    int len1 = sizeof(array1)/sizeof(char);
    char result1[len1]; // 提前分配输出数组内存

    printf("原数组：");
    print_char_array(array1, len1);
    printf("\n置换：");
    displace_print(cyclic_expr);
    displace_apply(cyclic_expr, array1, result1, len1, sizeof(char));
    printf("\n置换后：");
    print_char_array(result1, len1);
    printf("\n\n");

    // 测试2：组合置换（含重复元素，需化简）：(1 2) · (2 3) 作用于整数数组 {10,20,30,40}
    printf("=== 测试2：组合置换化简 (1 2) · (2 3) 作用于整数数组 ===\n");
    int cyclic2[] = {2, 3};
    DisplaceExpression *cyclic_expr2 = cyclic_displace_create(cyclic2, sizeof(cyclic2)/sizeof(int));
    DisplaceExpression *composite_expr = composite_displace_create(
        (DisplaceExpression *[]){cyclic_expr, cyclic_expr2}, 2
    );
    int array2[] = {10, 20, 30, 40};
    int len2 = sizeof(array2)/sizeof(int);
    int result2[len2]; // 输出数组

    printf("原数组：");
    print_int_array(array2, len2);
    printf("\n化简前置换：");
    displace_print(composite_expr);
    DisplaceExpression *simplified_expr = displace_simplify(composite_expr, len2);
    printf("\n化简后置换：");
    displace_print(simplified_expr);
    displace_apply(simplified_expr, array2, result2, len2, sizeof(int));
    printf("\n置换后：");
    print_int_array(result2, len2);
    printf("\n\n");

    // 测试3：恒等置换作用于字符串数组（自定义类型示例）
    printf("=== 测试3：恒等置换作用于字符串数组 ===\n");
    DisplaceExpression *empty_expr = empty_displace_create();
    const char *array3[] = {"apple", "banana", "cherry"};
    int len3 = sizeof(array3)/sizeof(char *);
    const char *result3[len3]; // 输出数组（指针数组，无需额外分配内存）

    printf("原数组：");
    for (int i = 0; i < len3; i++) {
        printf("\"%s\"", array3[i]);
        if (i != len3 - 1) printf(", ");
    }
    printf("\n置换：");
    displace_print(empty_expr);
    displace_apply(empty_expr, array3, result3, len3, sizeof(char *));
    printf("\n置换后：");
    for (int i = 0; i < len3; i++) {
        printf("\"%s\"", result3[i]);
        if (i != len3 - 1) printf(", ");
    }
    printf("\n");

    // 释放资源
    displace_destroy(cyclic_expr2);
    displace_destroy(composite_expr);
    displace_destroy(simplified_expr);

    return 0;
}